package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/number-of-people-aware-of-a-secret/">2327. 知道秘密的人数</a>
 */
private class Solution2327 {
    /*
    位置标记:       |   |   |   |   |   |   |   |   |   |   |   |   |   |
    遗忘延时:       0   0   0   1   0   1   1   1   2   2   3   4   5   7   9   12  16  21
    新增延时:       0   1   0   1   1   1   2   2   3   4   5   7   9   12  16  21
    每日增加:       0   1   1   1   2   2   3   4   5   7   9   12  16  21
    当前人数:   1   1   2   3   3   5   6   8   11  14  19  25  33  44  58


    位置标记:       |   |   |   |   |
    遗忘延时:       0   0   0   1   0   1   1   1   2
    新增延时:       0   1   0   1   1   1   2
    每日增加:       0   1   1   1   2
    当前人数:   1   1   2   3   3   5
     */
    fun peopleAwareOfSecret(n: Int, delay: Int, forget: Int): Int {
        val fd = IntArray(forget)
        fd[forget - 1] = 1
        val ud = IntArray(delay)
        ud[delay - 1] = 1
        var fp = 0
        var up = 0
        var c: Long = 1
        var today: Long = 0
        val mod = 1000000007
        var cn = n
        while (cn-- > 1) {
            today += (ud[up] + mod - fd[fp]) % mod
            today %= mod
            c += (today + mod - fd[fp]) % mod
            c %= mod
            ud[up] = today.toInt()
            fd[fp] = today.toInt()
            fp = (fp + 1) % forget
            up = (up + 1) % delay
        }
        return c.toInt()
    }
}

fun main() {
    println(Solution2327().peopleAwareOfSecret(684, 18, 496))
}